BOJ_2352_반도체 설계

[LIS(Longest Increasing Subsequence) 알고리즘의 응용 문제

|1|2|3|4|5|6| 의 포트를 각각
|4|2|6|3|1|5| 에 꽂아야 한다

단, 연결선이 서로 꼬이지 않아야 하는 것이 이 문제의 핵심이다
즉, 포트는 항상 이전에 꽂힌 선보다 더 높은 숫자의 포트에 꽂힌다
여기까지 생각했으면 LIS를 활용해서 최장 부분 수열을 구하는 문제라는 걸 알 수 있다
그리고 최장 부분 수열의 길이를 구하는 것이므로
이분 탐색만을 활용해서 푸는 것도 가능하다

문제 N이 40000이기 때문에 dp 방식의 LIS로 풀면 시간 초과가 난다
그런데 어째서인지 시간 초과를 확인할 겸 시험 삼아 제출했는데 통과 되었다
의문이지만 이분탐색을 사용해서 푸는 게 맞는 풀이법이다!

DP로 푼 코드

package solve.BJO;  
  
import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.Arrays;  
import java.util.stream.Stream;  
  
public class BJO_2352_반도체_설계 {  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
  
        int n = Integer.parseInt(br.readLine());  
        int[] ports = Stream.of(br.readLine().split(" ")).mapToIntparseInt).toArray(;  
  
        // 가장 긴 증가하는 수열 문제  
        // port에서 가장 긴 증가하는 수열의 길이를 출력하면 된다  
        int[] dp = new int[n + 1];  
        Arrays.fill(dp, 1);  
  
        for (int i = 0; i < n; i++) {  
            int port = ports[i];  
            for (int j = 0; j < i; j++) {  
                if (ports[j] < port) {  
                    dp[i] = Math.max(dp[i], dp[j] + 1);  
                }  
            }  
        }  
  
        System.out.println(Arrays.stream(dp).max().getAsInt());  
    }  
}

이분탐색으로 푼 코드

package solve.BJO;  
  
import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  
  
public class BJO_2352_반도체_설계_이분탐색 {  
    public static void main(String[] args) throws IOException {  
        // 입력  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        int n = Integer.parseInt(br.readLine());  
        StringTokenizer st = new StringTokenizer(br.readLine());  
  
        int[] ports = new int[n];  
        for (int i = 0; i < n; i++) {  
            ports[i] = Integer.parseInt(st.nextToken());  
        }  
  
        int[] lis = new int[n];  
        int length = 0;  
  
        for (int port : ports) {  
            int pos = binarySearch(lis, port, 0, length);  
            lis[pos] = port;  
  
            if (pos == length) {  
                length++;  
            }  
        }  
  
        System.out.println(length);  
    }  
  
    public static int binarySearch(int[] lis, int target, int start, int end) {  
        while (start < end) {  
            int mid = start + (end - start) / 2;  
            if (lis[mid] < target) {  
                start = mid + 1;  
            } else {  
                end = mid;  
            }  
        }  
        return start; // end여도 마찬가지  
    }  
}